home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 July / EnigmA AMIGA RUN 09 (1996)(G.R. Edizioni)(IT)[!][issue 1996-07 & 08][EARSAN CD VIII].iso / earcd / dev1 / vbcc.lha / vbcc / cp.c < prev    next >
C/C++ Source or Header  |  1996-05-15  |  13KB  |  348 lines
  1. /*  $VER: vbcc (cp.c) V0.3     */
  2. /*  verfuegbare Kopien und copy propagation */
  3.  
  4. #include "opt.h"
  5.  
  6.  
  7. /*  fuer verfuegbare Kopien */
  8. unsigned int ccount;
  9. size_t csize;
  10. struct IC **clist;
  11.  
  12. /*  alle Assignments, globaler oder Adr. fuer propagation etc.         */
  13. unsigned char *cp_globals,*cp_address,*cp_statics,*cp_drefs,*cp_act,*cp_dest;
  14. /*  alle Kopieranweisungen, die eine best. Variable als Quelle haben    */
  15. unsigned char **copies;
  16.  
  17. void available_copies(struct flowgraph *fg)
  18. /*  berechnet die verfuegbaren Kopien fuer jeden Block      */
  19. {
  20.     struct flowgraph *g;struct IC *p;unsigned char *tmp;int changed,pass,i;
  21.     /*  cp_gen und cp_kill fuer jeden Block berechnen   */
  22.     if(DEBUG&1024) printf("analysing available copies\n");
  23.     tmp=mymalloc(csize);
  24.     g=fg;
  25.     while(g){
  26.         g->cp_in=mymalloc(csize);
  27.         memset(g->cp_in,0,csize);
  28.         g->cp_out=mymalloc(csize);
  29.         memset(g->cp_out,0,csize);
  30.         g->cp_gen=mymalloc(csize);
  31.         memset(g->cp_gen,0,csize);
  32.         g->cp_kill=mymalloc(csize);
  33.         memset(g->cp_kill,0,csize);
  34.         p=g->end;
  35.         while(p){
  36.             if(p->code==CALL){
  37.                 memcpy(tmp,cp_globals,csize);
  38.                 bvunite(tmp,cp_statics,csize);
  39.                 bvunite(tmp,cp_address,csize);
  40.                 bvunite(tmp,cp_drefs,csize);
  41.                 bvdiff(tmp,g->cp_gen,csize);
  42.                 bvunite(g->cp_kill,tmp,csize);
  43.             }
  44.             i=p->copyindex;
  45.             if(i>=0){
  46.                 if(i>=ccount) ierror(0);
  47.                 if(clist[i]->copyindex!=i) ierror(0);
  48.                 if(!BTST(g->cp_kill,i)) BSET(g->cp_gen,i);
  49.             }
  50.             if(p->z.flags&VAR){
  51.                 struct Var *v;
  52.                 v=p->z.v;
  53.                 i=v->index;
  54.                 if(i<0) ierror(0);
  55.                 if(i>=vcount) ierror(0);
  56.                 memcpy(tmp,copies[i],csize);
  57.                 if(v->flags&USEDASADR){
  58.                     bvunite(tmp,cp_drefs,csize);
  59.                 }
  60.                 if(v->nesting==0||v->storage_class==EXTERN){
  61.                     bvunite(tmp,cp_drefs,csize);
  62.                 }
  63.                 if(p->z.flags&DREFOBJ){
  64.                     bvunite(tmp,cp_globals,csize);
  65.                     bvunite(tmp,cp_address,csize);
  66.                     bvunite(tmp,cp_drefs,csize);
  67.                 }
  68.                 if(i<rcount) bvunite(tmp,copies[i+vcount-rcount],csize);
  69.                 bvdiff(tmp,g->cp_gen,csize);
  70.                 bvunite(g->cp_kill,tmp,csize);
  71.             }
  72.  
  73.             if(p==g->start) break;
  74.             p=p->prev;
  75.         }
  76.         if(g==fg){
  77.             memset(g->cp_in,0,csize);
  78.             memcpy(g->cp_out,g->cp_gen,csize);
  79.         }else{
  80.             memset(g->cp_out,UCHAR_MAX,csize);
  81.             bvdiff(g->cp_out,g->cp_kill,csize);
  82.         }
  83.         g=g->normalout;
  84.     }
  85.     /*  cp_in und cp_out fuer jeden Block berechnen */
  86.     /*  out(b)=U-gen(B) vorinitialisiert und        */
  87.     /*  in(B0)=0, out(B0)=gen(B0)                   */
  88.     if(DEBUG&1024) {printf("pass:");pass=0;}
  89.     do{
  90.         if(DEBUG&1024) {printf(" %d",++pass);fflush(stdout);}
  91.         changed=0;
  92.         g=fg->normalout;    /*  in B0 aendert sich nichts   */
  93.         while(g){
  94.             struct flowlist *lp;
  95.             /*  in(B)=Schnitt out(P) mit P Vorgaenger von B */
  96.             lp=g->in;
  97.             i=0;    /*  Flag fuer ersten Vorgaenger */
  98.             while(lp){
  99.                 if(!lp->graph) ierror(0);
  100.                 if(lp->graph->branchout==g||!lp->graph->end||lp->graph->end->code!=BRA){
  101.                     if(i){
  102.                         bvintersect(g->cp_in,lp->graph->cp_out,csize);
  103.                     }else{
  104.                         memcpy(g->cp_in,lp->graph->cp_out,csize);i=1;
  105.                     }
  106.                 }
  107.                 lp=lp->next;
  108.             }
  109.             /*  out(b)=gen(B) U (in(B)-kill(B)  */
  110.             memcpy(tmp,g->cp_in,csize);
  111.             bvdiff(tmp,g->cp_kill,csize);
  112.             bvunite(tmp,g->cp_gen,csize);
  113.             if(!bvcmp(tmp,g->cp_out,csize)){changed=1;memcpy(g->cp_out,tmp,csize);}
  114.             g=g->normalout;
  115.         }
  116.     }while(changed);
  117.     if(DEBUG&1024) printf("\n");
  118.     free(tmp);
  119. }
  120.  
  121. int compare_cp(const void *a1,const void *a2)
  122. /*  Stub fuer compare_objs, damit als Vergleichsfunktion fuer qsort geht */
  123. {
  124.     struct IC *p1,*p2;int i1,i2;
  125.     p1=*((struct IC **)a1);p2=*((struct IC **)a2);
  126.     if(!p1||!p2) ierror(0);
  127.     i1=p1->typf; i2=p2->typf;
  128.     if(i1<i2) return(-1);
  129.     if(i1>i2) return(1);
  130.     i1=compare_objs(&p1->q1,&p2->q1,p1->typf);
  131.     if(i1) return(i1);
  132.     i1=compare_objs(&p1->z,&p2->z,p1->typf);
  133.     return(i1);
  134. }
  135.  
  136. void num_copies(void)
  137. /*  numeriert alle einfachen Kopieranweisungen  */
  138. {
  139.     struct IC *p;struct Var *v;int i,n,c;
  140.     if(DEBUG&1024) printf("numerating copies loop1\n");
  141.     ccount=0;
  142.     for(p=first_ic;p;p=p->next){
  143.         if(p->code==ASSIGN&&(p->q1.flags&(VAR/*|VARADR*/))==VAR) p->copyindex=ccount++;
  144.             else            p->copyindex=-1;
  145.     }
  146.     csize=(ccount+CHAR_BIT-1)/CHAR_BIT;
  147.     if(DEBUG&1024) printf("ccount=%lu, csize=%lu\n",(unsigned long)ccount,(unsigned long)csize);
  148.     clist=mymalloc(ccount*sizeof(struct IC *));
  149.     cp_globals=mymalloc(csize);
  150.     memset(cp_globals,0,csize);
  151.     cp_statics=mymalloc(csize);
  152.     memset(cp_statics,0,csize);
  153.     cp_address=mymalloc(csize);
  154.     memset(cp_address,0,csize);
  155.     cp_drefs=mymalloc(csize);
  156.     memset(cp_drefs,0,csize);
  157.     copies=mymalloc(vcount*sizeof(unsigned char *));
  158.     if(DEBUG&1024){ printf("num_copies loop2\n");}
  159.     for(p=first_ic;p;p=p->next){
  160.         if(p->copyindex>=0){
  161.             clist[p->copyindex]=p;
  162.         }
  163.     }
  164.     if(DEBUG&1024){ printf("sorting copies\n");}
  165.     if(ccount>1) qsort(clist,ccount,sizeof(struct IC *),compare_cp);
  166.     if(DEBUG&1024){ printf("renumbering copies\nnum_copies loop3\n");}
  167.     if(ccount>0){   /*  Aufpassen, da ccount unsigned!  */
  168.         for(c=0;c<ccount-1;c++){
  169.             if(!compare_cp(&clist[c],&clist[c+1]))
  170.                 clist[c+1]->copyindex=clist[c]->copyindex;
  171.         }
  172.     }
  173.     if(DEBUG&1024) printf("re-sorting copies\n");
  174.     /*  wieder in die richtige Reihenfolge bringen  */
  175.     for(p=first_ic;p;p=p->next)
  176.         if(p->copyindex>=0) clist[p->copyindex]=p;
  177.  
  178.     for(i=0;i<vcount;i++){
  179.         copies[i]=mymalloc(csize);
  180.         memset(copies[i],0,csize);
  181.     }
  182.  
  183.     if(DEBUG&1024) printf("numerating copies loop4\n");
  184.     for(p=first_ic;p;p=p->next){
  185.         i=p->copyindex;
  186.         if(i>=0){
  187. /*            clist[i]=p;*/
  188.             v=p->z.v;
  189.             n=v->index;
  190.             if(p->z.flags&DREFOBJ) n+=vcount-rcount;
  191.             if(n<0||n>=vcount) ierror(0);
  192.             BSET(copies[n],i);
  193.             if(v->nesting==0||v->storage_class==EXTERN) BSET(cp_globals,i);
  194.             if(p->z.flags&DREFOBJ) BSET(cp_drefs,i);
  195.             if(v->storage_class==STATIC) BSET(cp_statics,i);
  196.             if(v->flags&USEDASADR) BSET(cp_address,i);
  197.             v=p->q1.v;
  198.             n=v->index;
  199.             if(p->q1.flags&DREFOBJ) n+=vcount-rcount;
  200.             if(n<0||n>=vcount){pric2(stdout,p);printf("n=%d\n",n); ierror(0);}
  201.             BSET(copies[n],i);
  202.             if(v->nesting==0||v->storage_class==EXTERN) BSET(cp_globals,i);
  203.             if(p->q1.flags&DREFOBJ) BSET(cp_drefs,i);
  204.             if(v->storage_class==STATIC) BSET(cp_statics,i);
  205.             if(v->flags&USEDASADR) BSET(cp_address,i);
  206.  
  207.         }
  208.     }
  209.     if(DEBUG&2048){
  210.         printf("copy instructions:\n");
  211.         for(i=0;i<ccount;i++){
  212.             printf("%3d: ",i);pric2(stdout,clist[i]);
  213.             if(clist[i]->copyindex!=i) ierror(0);
  214.         }
  215.     }
  216. }
  217. void print_cp(unsigned char *cp)
  218. {
  219.     int i;
  220.     if(!cp) printf("available copies not available\n");
  221.     for(i=0;i<ccount;i++)
  222.         if(BTST(cp,i)){printf("%3d: ",i);pric2(stdout,clist[i]);}
  223. }
  224. int cprop(struct obj *o,int target,int size)
  225. /*  ersetzt gegebenenfalls  Kopien, noch aendern, so dass Pointer in DREFOBJS ersetzt werden wie bei target */
  226. {
  227.     struct IC *p,*f=0;int i;
  228.     i=o->v->index;
  229.     if(!target&&o->flags&DREFOBJ) i+=vcount-rcount;
  230.     if(i<0||i>=vcount) ierror(0);
  231.     memcpy(tmp,cp_act,csize);
  232.     bvintersect(tmp,copies[i],csize);
  233.     /*  waehrend diesem Durchlauf geaenderte Kopieranweisungen lieber nicht */
  234.     /*  beachten                                                            */
  235.     bvdiff(tmp,cp_dest,csize);
  236.     for(i=0;i<ccount;i++){
  237.         if(BTST(tmp,i)){
  238.             p=clist[i];
  239.             if((!size||size==p->q2.reg)&&p->z.v==o->v&&p->q1.v!=o->v&&zleqto(p->z.val.vlong,o->val.vlong)){
  240.                 if(((o->flags&DREFOBJ)&&!(p->q1.flags&DREFOBJ))||!(p->q1.flags&DREFOBJ)){
  241.                     if(DEBUG&1024){ printf("can replace <%s> by copy:\n",o->v->identifier);pric2(stdout,clist[i]);}
  242.                     *o=p->q1;
  243.                     if(target){
  244.                         o->flags|=DREFOBJ;
  245.                         if((o->flags&(VARADR|DREFOBJ))==(VARADR|DREFOBJ))
  246.                             o->flags&=~(VARADR|DREFOBJ);
  247.                         /*  Wenn eine Variable, dadurch zu einer DREF-Variable  */
  248.                         /*  wird, muss num_vars spaeter erneut gemacht werden   */
  249.                         if(o->v->index>=rcount) return(2);
  250.                     }
  251.                     return(1);
  252.                 }
  253.             }
  254.         }
  255.     }
  256.     return(0);
  257. }
  258. int copy_propagation(struct flowgraph *fg,int global)
  259. /*  gibt Kopien weiter  */
  260. {
  261.     struct flowgraph *g; struct obj old;int or;
  262.     struct IC *p;struct Var *v;int i,changed,r;
  263.     if(DEBUG&1024) printf("searching copies\n");
  264.     cp_act=mymalloc(csize);
  265.     cp_dest=mymalloc(csize);
  266.     memset(cp_dest,0,csize);
  267.     tmp=mymalloc(csize);
  268.     g=fg;changed=0;
  269.     while(g){
  270.         if(!global) memset(cp_act,0,csize); else memcpy(cp_act,g->cp_in,csize);
  271.         p=g->start;
  272.         while(p){
  273.             int size;
  274.             if(p->code==ASSIGN||p->code==PUSH) size=p->q2.reg;
  275.                 else size=0;
  276. /*            print_copies(cp_act); pric2(stdout,p);*/
  277.             r=0;
  278.             if((p->q1.flags&(VAR|VARADR))==VAR){
  279.                 r|=cprop(&p->q1,0,size);
  280.                 r|=cprop(&p->q1,1,size);
  281.             }
  282.             if((p->q2.flags&(VAR|VARADR))==VAR){
  283.             /*  passt auf, dass USEQ2ASZ nicht verletzt wird, ist dabei */
  284.             /*  aber nicht sehr effizient (evtl. koennte kommutiert     */
  285.             /*  werden, o.ae.)                                          */
  286.                 if(!USEQ2ASZ){ old=p->q2;or=r;}
  287.                 r|=cprop(&p->q2,0,size);
  288.                 r|=cprop(&p->q2,1,size);
  289.                 if(!USEQ2ASZ&&!compare_objs(&p->q2,&p->z,p->typf)){
  290.                     if(DEBUG&1024) printf("copy propagation taken back, because of USEQ2ASZ\n");
  291.                     p->q2=old;
  292.                     r=or;
  293.                 }
  294.             }
  295.             if((p->z.flags&(VAR|VARADR|DREFOBJ))==(VAR|DREFOBJ)){
  296.             /*  passt auf, dass USEQ2ASZ nicht verletzt wird, ist dabei */
  297.             /*  aber nicht sehr effizient (evtl. koennte kommutiert     */
  298.             /*  werden, o.ae.                                           */
  299.                 if(!USEQ2ASZ){ old=p->z;or=r;}
  300.                 r|=cprop(&p->z,1,size);
  301.                 if(!USEQ2ASZ&&!compare_objs(&p->q2,&p->z,p->typf)){
  302.                     if(DEBUG&1024) printf("copy propagation taken back, because of USEQ2ASZ\n");
  303.                     p->z=old;
  304.                     r=or;
  305.                 }
  306.             }
  307.             if(r&&p->copyindex) BSET(cp_dest,p->copyindex);
  308.             changed|=r;
  309.             if(p->z.flags&VAR){
  310.                 v=p->z.v;i=v->index;
  311.                 if(i<0||i>=vcount) ierror(0);
  312.                 if(v->nesting==0||v->storage_class==EXTERN)
  313.                     bvdiff(cp_act,cp_drefs,csize);
  314.                 if(p->z.flags&DREFOBJ){
  315.                     bvdiff(cp_act,cp_drefs,csize);
  316.                     bvdiff(cp_act,cp_address,csize);
  317.                     bvdiff(cp_act,cp_globals,csize);
  318.                 }
  319.                 bvdiff(cp_act,copies[i],csize);
  320.                 if(i<rcount) bvdiff(cp_act,copies[i+vcount-rcount],csize);
  321.                 if(p->copyindex>=0) BSET(cp_act,p->copyindex);
  322.             }
  323.             if(p->code==CALL){
  324.                     bvdiff(cp_act,cp_drefs,csize);
  325.                     bvdiff(cp_act,cp_address,csize);
  326.                     bvdiff(cp_act,cp_globals,csize);
  327.                     bvdiff(cp_act,cp_statics,csize);
  328.             }
  329.             if(p==g->end) break;
  330.             p=p->next;
  331.         }
  332.         g=g->normalout;
  333.     }
  334.     free(cp_act);
  335.     free(cp_dest);
  336.     free(tmp);
  337.     free(clist);
  338.     free(cp_globals);
  339.     free(cp_statics);
  340.     free(cp_address);
  341.     free(cp_drefs);
  342.     for(i=0;i<vcount;i++) free(copies[i]);
  343.     free(copies);
  344.     gchanged|=changed;
  345.     return(changed);
  346. }
  347.  
  348.